CCPC 热身赛A Square Counting

Posted on | In ,

热身赛光荣打铁，只能回来补题。。

思路

题目来源Kickstart Round A 2017 Problem A。大致意思是从一个m*n矩形中能选出多少个正方形（这里给的是点数，我们默认m-1,n-1）。对于这个问题我们把斜着的正方形和正常的正方形分开考虑。
对于正常的正方形有：
gs1
对于斜着的正方形有：（画张图考虑后能发现斜着且撑满的正方形只有k-1个，然后从小正方形到大正方形累加）
gs2
化简可得
gs3
利用平方和公式和立方和公式我们能O(1)求出答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
#define ms(a,val) memset((a),(val),(sizeof(a)))

using namespace std;

const int mod=1e9+7;
struct mint{
    int x;
    mint():x(0){};
    mint(int s){
        x=s;if(x<mod&&x>=0)return;
        x%=mod;if(x<0)x+=mod;
    }
    mint(ll s){int ts=s%mod;if(ts<0)ts+=mod;x=ts;}
    mint& operator +=(mint t){
        if((x+=t.x)>=mod)x-=mod;return *this;
    }
    mint& operator -=(mint t){
        if((x+=mod-t.x)>=mod)x-=mod;return *this;
    }
    mint& operator *=(mint t){x=(ll)x*t.x%mod;return *this;}
    mint& operator /=(mint t){return *this*=t.inv();}
    mint operator -()const {if(x)return mod-x;return 0;}
    mint operator +(mint t)const{return mint(*this)+=t;}
    mint operator -(mint t)const{return mint(*this)-=t;}
    mint operator *(mint t)const{return mint(*this)*=t;}
    mint operator /(mint t)const{return mint(*this)/=t;}
    mint pow(ll k)const{
        mint r=1,a=x;
        for(;k;k>>=1,a*=a)if(k&1)r*=a;
        return r;
    }
    mint inv()const{return mint(x).pow(mod-2);}
};
int main(){
    int t;
    ll tm,tn;
    scanf("%d",&t);
    for(int z=0;z<t;z++){
        scanf("%lld%lld",&tm,&tn);
        mint m(tm-1),n(tn-1),mb(min(tm-1,tn-1));
        mint ans(0);
        ans+=(m*n+m+n+mint(1))*(mint(1)+mb)*mb/mint(2)-(m+n+2)*mb*(mb+mint(1))*(mint(2)*mb+mint(1))/mint(6)+(mb*(mb+mint(1))/mint(2))*(mb*(mb+mint(1))/mint(2));
        printf("Case #%d: %d\n",z+1,ans.x);
    }

    return 0;
}